perm filename GEM[00,BGB]2 blob
sn#111638 filedate 1974-07-17 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00014 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00003 00002 {[C⊂G<NαGEOMETRIC MODELING THEORY.λ30I425,0P6JCFA} SECTION 1.
C00006 00003 [1.1 Kinds of Geometric Models.]
C00008 00004 For a naive start, first consider a 3-D array in which each
C00012 00005
C00016 00006
C00020 00007
C00023 00008
C00026 00009
C00029 00010 {|λ10JA}
C00031 00011 [1.2 Polyhedron Definitions and Properties.]
C00036 00012
C00041 00013 [1.3 Camera, Light and Image Modeling.]
C00047 00014 [1.4 Related Modeling Work.]
C00051 ENDMK
C⊗;
{[C;⊂G;<N;αGEOMETRIC MODELING THEORY.;λ30;I425,0;P6;JC;FA} SECTION 1.
{JC;FD} GEOMETRIC MODELING THEORY.
{λ10;W250;JAFA}
1.0 Introduction to Geometric Modeling.
1.1 Kinds of Geometric Models.
1.2 Polyhedron Definitions and Properties.
1.3 Camera, Light and Image Modeling.
1.4 Related Modeling Work.
{λ30;W0;I950,0;JUFA}
[1.0 Introduction to Geometric Modeling.]
In the specific context of computer vision and graphics,
<geometric modeling> refers to constructing computer representations
of physical objects, cameras, images and light for the sake of
simulating their behavior. In Artificial Intelligence, a geometric
model is a kind of world model; ignoring subtleties, geometric world
modeling is distinguished from semantic and logical world modeling in
that it is quantitative and numerical rather than qualitative and
symbolic. The notion of a world model requires an external world
environment to be modeled, an internal computer environment to hold
the model, and a task performing entity to use the model. In
Geometry, modeling is a synthetic problem, like a construction with
ruler and straight edge, modeling problems require an algorithmic
solution rather than a proof. The word <geometric> is an appropriate
adjective to modeling in that it is a combination of the greek words
⊂gho⊃ (world) and ⊂metria⊃ (measuring) which is exactly the activity
to be automated. {Q}
[1.1 Kinds of Geometric Models.]
The main problem of geometric modeling is to invent good
methods for representing arbitrary physical objects in a computer. A
physical object (for the moment) is something solid, rigid, opaque,
and macroscopic with a mathematically well behaved surface. Physical
objects include: the earth, chairs, roads, and plastic toy horses.
Such objects can be moved about in space with the restriction that
two objects can not occupy the same space at the same time. The
scope of the modeling problem can be appreciated by examining the
virtues and drawbacks of the models in box 1.1.
{|;λ10;JA}
BOX 1.1{JC} TEN KINDS OF GEOMETRIC MODELS.
{↓}
Space Oriented:
1. 3-D Space Array.
2. Recursive Cells.
3. 3-D Density Function.
4. 2-D Surface Functions.
5. Parametric Surface Functions.
{↑;W640;}
Object Oriented:
6. Manifolds.
7. Polyhedra.
8. Volume Elements.
9. Cross Sections.
10. Skeletons.
{|;λ30;JU}
For a naive start, first consider a 3-D array in which each
element indicates the presence or absence of solid matter in a cube
of space. Such a 3-D space array has the very desirable properties
of <spatial addressing> and <spatial uniqueness> in their most direct
and natural form. Spatial addressing refers to finding out what the
model contains within a distance R of a locus X,Y,Z; spatial
uniqueness refers to modeling the property that physical solids can
not occupy the same space. The main drawback of the 3-D space array
model is illustrated by the apparently legal FORTRAN statement:
{JC} DIMENSION SPACE(10000,10000,10000)
\The problem with such a dimension statement is that no present day
computer memory is large enough to contain a 10↑15 element array.
Smaller space arrays can be useful but necessarily can not model
large volumes with high resolution. A further drawback of space
arrays is that objects and surfaces are not readily accessible as
entities; that is a space array lacks the desirable property of
<object coherence>. Coherence is the <sine qua non> of an object;
physical objects tend to hang together, to be self connected, in
short to be coherent.
The space array idea can be salvaged by grouping blocks of
elements with the same value together, the addressing process
becomes more complicated but the overall memory required is reduced
and the two desired properties can be maintained. One way of doing
this (which has been discovered in several applications) is
<recursive cells>; the whole space is considered to be a cell; if the
space is not homogeneous than the first cell is divided into two (or
four or eight) sub cells and the criterion is applied again. This
technique allows the spatial sorting of objects, if the object
models can be subdivided at each recursion without losing the
properties of the objects.
Another naive modeling idea is that
arbitrary objects can be expressed as algebraic functions. In
physics, physical objects are frequently referred to as three
dimensional density functions W=RHO(X,Y,Z). Unfortunately such
density functions can not be written out for objects such as a typing
chair or a plastic horse without resorting to a programming language
or an extensive table (which is equivalent to the space array model).
Some objects however are essentially 2-D and can be approximated by a
surface function Z = F(X,Y). For example landscape may be represented
by geodetic maps in such a 2-D fashion.
By definition, a function is single valued; consequently the
description of even modestly complicated objects can not be expressed
directly as a single function of orthogonal rectilinear space
coordinates X, Y and Z. It is necessary either to adopt parametric
functions or to subdivide the object into portions that can be
described by simple functions of Cartesian variables. The former
course involves establishing a system of surface coordinates (U,V) or
latitudes and longitudes on the object in which functions for the
X,Y,Z locus of the object's surface can be constructed. The advantage
of parametric functions is that extended arbitrary curve surfaces
might be expressed; some of the disadvantages are that parametric
curves may be self intersecting, they are not easy to modified
locally, and the functions become impractically complex before the
shapes of mundane artifacts can be achieved. Thus parametric
representation is combined with subdividing the object into portions,
which is the latter course called <segmentation>. The process of
usefully segmenting an object without destroying its coherence is a
major theme of modeling research which requires the combination of
appropriate spatial, functional and objective representations.
In passing from space oriented models to object oriented
models, observe that the same dichotomy appears at the frontiers of
physics where on the one hand the quantum field particle wave theory
of objects has yet to be reconciled with the general relativistic
theory of the space that contains the objects. Also in passing, I
wish to note that sophisticated representations of time is beyond the
scope of this present discussion, although an advanced problem
solving robot will want to run world simulations along multiple time
paths.
After existence in space and time, another general property
of physical objects is that they can be enclosed by an unbroken two
dimensional surface with an unabiguous inside and outside; which
touchs upon the mathematical topic (celebrated in song by Tom Lehrer)
of the algebraic topology of locally Euclidean transitions of
infinitely differentiable oriented Riemann manifolds. A <manifold>
is the mathematical abstraction of a surface; a <Riemann> manifold
has a metric function; an <oriented> manifold has a unambiguous
inside and an outside; the phrase <infinitely differentiable> can be
taken to mean that the surface is smooth and continuous; and the
phrase <locally Euclidean transitions> refers to the process of
segmenting the object into portions that can be approximated by
relatively simple functions. In particular, the 2-D Riemann
submanifold embedded in 3-D Euclidean space is the mathematical
object that comes closest to representing the shape and extent of the
surface of a physical object; such manifolds are conveniently
approached through the topology of surfaces which in turn in is
conveniently approached by means of polyhedra.
The topology of a 2-D Riemann submanifold embedded in a 3-D
Euclidean space is composed of three kinds of simplex: the 0-Simplex
(or vertex), the 1-Simplex (or edge), and the 2-Simplex (or
triangle). In topological analysis 2-D Riemann submanifolds may be
divided into faces, edges and vertices such that Eulers equations
F-E+V=2-2*H is satisfied (where F is the number of faces, E is the
number of edges, V is the number of vertices and H is the genus or
number of handles of the manifold); and such that the surface of the
manifold can be approximated by local functions over each face which
are Euclidean and which fit together smoothly at all the edges. By
introducing a sufficient (but finite) number of triangles the
manifold can be approximated to within an epsilon, by constant
functions; yielding the geometric object called the <polyhedron>.
The main inherent advantage of a polyhedral model is its
coherent surface topology of faces, edges and vertices. Such a
surface can be subdivided without losing its coherence or the
coherence of the object. The disadvantages of polyhedra include the
lack of spatial uniqueness and spatial addressing which necessitates
computation to be done to detect and prevent spatial conflict and to
find the portions of an entity occupying a given volume. Another
feature of polyhedra (which can be an advantage or disadvantage) is
that all the <Gaussian> curvature happens suddenly at the vertices;
however by associating higher ordered approximation functions with
each face the model of a 2-D Riemann manifold can be recovered,
which is recognizible as a more conventional curved object
representation.
Returning to the survey, arbitrary objects can also be
described by listing a set of cross sections taken at a sufficient
number of cutting planes; this is how the shape of a ship's hull or
an airplane's wing is specified. Cross sections have the interesting
feature of good space modeling on one axis. Forsaking arbitrary
shaped objects, large classes of things can be described in terms of
a small set of basic volume elements. For example, Larry Roberts
(ref **) and others have built models of familar objects using only
rectangular and triangular right prisms. Although, arbitrary solid
polyhedra can be constructed out of tetrahedrons (the 3-simplex); no
significant general modeling system exists using this potentially
interesting approach.
Skeletal models are based on abstracting an object into a
stick figure and by associating a diameter or set of cross sections
with the sticks. In particular, spine cross section models have been
pursued at Stanford by Agin, Binford and Nervatia. Spine cross
section models have the advantage of being able to express many
objects in a concise form suitable for recognition, however spine
cross section models can not be used directly for arbitrary shapes.
Finally, it is useful to represent physical objects by a weak
geometric models such as by a sets of spheres or sets of surface
points. It is interesting to note that the <reality> that the robot
in Winograd's thesis could talk about, was a blocks world based on a
geometric model consisting only of points, size of block, and a two
page LISP subroutine named FINDSPACE.
Beyond the particular kinds of geometric models, four general
purpose modeling techniques deserve special mention and isolation:
Prototype-Instance Structure, Parts-Tree Structure,
Resolution-Limited Structure, and Procedure-Generated Structure.
Superficially, the prototype-instance structure is a memory
efficiency technique of modeling by binding variables in a more
flexible and abstract model or prototype. Parts-tree structure is a
memory management technique of organizing the whole universe of
discourse as a tree data structure, where objects are composed of sub
objects. Resolution-Limited structure is a memory accessing
technique, where depending on a specified scale of interest different
models are retrieved or even generated. Finally, Procedure-Generated
Structure concerns the trade-off between storing and recomputing a
model; namely recomputing the details of a model as they are needed
is a good idea for extending computational resources to have a better
model. Now the danger to be avoided is to mistake the general
modeling techniques for the geometric model itself. Given a modeling
regime it can be improved by prototyping, parts-treeing,
resolution-limiting and procedural-generating; without a good basic
geometric model the general techniques amplified the background noise.
{|;λ10;JA}
BOX 1.2 {JC} DESIRABLE PROPERTIES FOR A GEOMETRIC MODEL.
{↓}
1. Spatial addressing.
2. Spatial uniqueness.
3. Object coherence.
4. Surface coherence.
5. Shape generality.
{↑;w500;}
6. Large extent with high resolution.
7. Readily modifiable.
8. Suitable for simulation.
9. Feasible memory and computation requirements.
10. Potential for automatic model acquistion.
{|;λ30;JU}
To the best of my knowledge, this survey is complete. As of
this year, 1974, there are no other significantly different kinds of
simple geometric models. The desirable properties that have turned up
in this survey are included in the list below. The final desirable
property is that there be some hope that the computer can derive the
model by measurements it can make itself, although it is quite likely
that one model will be best for input and another model will be best
for simulation.{Q}
[1.2 Polyhedron Definitions and Properties.]
In computational modeling, definitions are not used
formally, but are rather employed piecemeal in terms of individual
properties which may or may not be present as polyhedra are generated
and processed. In particular, the properties listed in box 1.3 (given
in order of relevance) can be taken as a working definition of a
polyhedron for modeling a physical object.
{|;λ10;JA}
BOX 1.3 {JC} PROPERTIES OF POLYHEDRA.
{JA,FA↓}
1. Eulerian.
2. Surface Homogeneity.
3. Trivalence.
4. Face Planarity.
5. Solidity.
6. Simply Connected Faces.
7. Face Convexity.
8. Aplanarity.
{↑;W600;}
Satisfies the Euler equation: F-E+V=2*B-2*H.
The polyhedron does not intersect itself.
All vertices and faces have three or more edges.
All the vertices of a face are coplanar.
The volume measure is non-zero, finite and positive.
Face perimeters have one loop of edges.
All the faces are convex.
Faces which share an edge are not coplanar.
{|;λ30;JU}
Topologically, the surface elements of a polyhedron form a
graph that satisfies Euler's F-E+V=2-2*H equation; where as before F,
E and V are the number of faces, edges and vertices of the
polyhedron; and where H is the number of holes in (or genus of) the
polyhedron. However, not all Eulerian graphs of faces, edges and
vertices correspond to the usual notion of a solid polyhedra without
the surface homogeneity and trivalence restrictions. Surface
homogeneity is the property that for any point on the polyhedron a
small enough sphere will cut from the surface a region homeomorphic
to a disk; this restriction implies that the surface can not
intersect itself and that edges can only belong to two different
faces. The trivalence restriction insures that their are no
degenerate two sided faces or one edged vertices; although a two
edged vertex has a reasonible interpretation it is excluded by
trivalence for the sake of face-vertex duality and canonical form.
The last property, of aplanarity of faces with a common edge, is also
for the sake of canonical form and is sacrificed to face convexity
when necessary.
Geometrically, the faces of a polyhedron are planar, that is
lie in a plane. It is also frequently relevant to further restricted
the faces of a polyhedron to be convex, that is every possible line
segment between points of a face is contained within the face. To
assure solidity, the volume measure must be restricted to be finite
and positive; this restriction orients the surface to have an
exterior and an interior in the expected fashion. This restriction
does not exclude exploiting the concept of negative volumes at some
later time (chapter 5); but it does exclude non-orientable structures
such as Mobius bands and Klein bottles for which the volume measure
will be undefined.
The working definition was derived from more formal
definitions such the following which defines a polyhedron as a
special kind of a two dimensional manifold:
{λ7;W100,1160;}
\"A polyhedron is a connected, unbounded two-dimensional
manifold formed by a finite set of non-re-entrant, simply-connected
plane polygons."{λ30;I∂-20,∂0;W0,1260;JR} - Coxeter (Ref **).
\A <connected> manifold is an entity that is not disjoint and
an <unbounded> manifold is one with no cuts or gaps in its surface,
that is no boundaries. A polyhedral manifold is composed of planar,
simply-connected, non-re-entrant polygons; that is flat polygons with
a perimeter of edges that form one loop that doesn't intersect
itself. The usual high school level definitions of a polyhedra are
inadequate in that they invariably apply only to convex polyhedra
and do not exclude the undesired cases such as self intersecting polyhedra.
To repeat, the polyhedron restrictions and properties are
directed towards modeling physical objects and are maintain or
verified by computational mechanisms; so that the word <polyhedron>
means the intent, rather than the fulfillment of any particular set
of defining properties.
{Q}
[1.3 Camera, Light and Image Modeling.]
Common to both computer graphics and vision is the necessity
to model cameras, light and images so that pictures may be
synthesized or analysized. The reader completely naive to camera
modeling is emphatically warned that all camera discussion in this
paper refers to a logical camera geometry rather than to a physical
camera geometry, the difference is illustrated in figure **.
The basic camera model has eight degrees of freedom, three
in location, three in orientation and two in projection:{λ10;
JA} Location: CX, CY, CZ Vector to camera lens center.
Orientation: WX, WY, WZ Orientation vector.
Projection: AR, FR Aspect Ratio and Focal Ratio.{λ30;JU}
\The orientation vector is explained in section 3.2,
the perspective projection is defined in section 3.3,
the automatic derivation of the camera parameters is the main topic of
chapter nine.
In modeling the behavior of light with respect to physical
objects, the most important and difficult property to mimic is that
most objects are opaque. The techniques required for modeling opaque
objects are presented in chapter four.
Finally, an image is a 2-D geometric object representing the
content of rectangle from the pattern of light of light formed by a
thin lens on a television vidicon. The video image is the interface
to the external reality. Image modeling is somewhat analogous to 3-D
geometric modeling, since the same tradeoffs between spatial
structures and object structure arise. A 2-D image may be
represented as a video raster, which is a 2-D space array or as a set
of feature loci which is an object oriented description. Image
structures and processors for generating and comparing image
representations will be discussed in chapters seven and eight.
Together camera, light and image modeling are the essential elements
required to apply a geometric model to computer vision. {Q}
[1.4 Related Modeling Work.]
Although geometric modeling per se has a long history and a
rich literature in Mathematics, Physics and Engineering; very little
such modeling has been done using a computer. Also the the level of
the modeling required for visual perception falls between the
generality typical in Physics and Mathematics and the specificality
typical of Engineering.
Computer Science research work in geometric modeling has
already been cited in section 1.2; other ideas are available from
computer graphics sources (ref **). In Mathematics, I have found the
work of the Canadian geometers Coxeter (ref ** and **) to be quite
useful along with the observations from polyhedral recreationalist
(cf ***) and the geometry textbooks (ref **). With the exception of
general relativistic gravitation theory (ref **), Geometry is not at
the frontier of either mathematics or physics. In engineering, books
on geodetic surveying, mechanical drawing and archetectural drawing
contain idea relevant to modeling particular classes of objects.